package sort;

import java.time.chrono.MinguoDate;
import java.util.*;
import java.util.stream.IntStream;

public class SortAlgorithm {
    /**
     * 冒泡排序
     *
     * @param arr 排序数组
     */
    static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }

    /**
     * 选择排序
     *
     * @param arr 排序数组
     */
    static void selectSort(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            int index = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[index]) {
                    index = j;
                }
            }
            int tmp = arr[i];
            arr[i] = arr[index];
            arr[index] = tmp;
        }
    }

    /**
     * 插入排序
     *
     * @param arr 排序数组
     */
    static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int index = i - 1, val = arr[i];
            while (index >= 0 && arr[index] > val) {
                arr[index + 1] = arr[index--];
            }
            arr[index + 1] = val;
        }
    }

    /**
     * 希尔排序
     *
     * @param arr 排序数组
     */
    static void shellSort(int[] arr) {
        for (int h = (arr.length >> 1) - 1; h > 0; h--) {
            for (int i = h; i < arr.length; i += h) {
                int index = i - h, val = arr[i];
                while (index >= 0 && arr[index] > val) {
                    arr[index + h] = arr[index];
                    index -= h;
                }
                arr[index + h] = val;
            }
        }
    }

    /**
     * 归并排讯
     *
     * @param arr 排序数组
     * @return 排序数组
     */
    static int[] mergeSort(int[] arr) {
        if (arr.length < 2) return arr;
        int l[] = mergeSort(Arrays.copyOfRange(arr, 0, arr.length >> 1)), r[] = mergeSort(Arrays.copyOfRange(arr, arr.length >> 1, arr.length));
        List<Integer> ret = new ArrayList<>();
        for (int i = 0, j = 0; i < l.length || j < r.length; ) {
            int n1 = i < l.length ? l[i] : Integer.MAX_VALUE, n2 = j < r.length ? r[j] : Integer.MAX_VALUE;
            if (n1 < n2) {
                ret.add(n1);
                i++;
            } else {
                ret.add(n2);
                j++;
            }
        }
        return ret.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * 快速排序
     *
     * @param arr 排序数组
     */
    static void quickSort(int[] arr) {
        Deque<int[]> stack = new LinkedList<>();
        stack.push(new int[]{0, arr.length - 1});
        while (!stack.isEmpty()) {
            int[] aa = stack.pop();
            int l = aa[0], r = aa[1];
            if (l < r) {
                int pivot = partition(arr, l, r);
                if (pivot - 1 > l) {
                    stack.push(new int[]{l, pivot - 1});
                }
                if (pivot + 1 < r) {
                    stack.push(new int[]{pivot + 1, r});
                }
            }
        }
    }

    private static int partition(int[] arr, int i, int j) {
        int pivot = arr[i], l = i + 1, r = j;
        while (l <= r) {
            while (l <= r && arr[l] <= pivot) ++l;
            while (l <= r && arr[r] >= pivot) --r;
            if (l >= r) break;
            int tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
        }
        arr[i] = arr[r];
        arr[r] = pivot;
        return r;
    }

    /**
     * 堆排序
     *
     * @param arr 排序数组
     */
    static void heapSort(int[] arr) {
        for (int i = (arr.length >> 1) - 1; i >= 0; --i) {
            heapify(arr, i, arr.length);
        }
        for (int i = arr.length - 1; i > 0; --i) {
            int tmp = arr[0];
            arr[0] = arr[i];
            arr[i] = tmp;
            heapify(arr, 0, i);
        }
    }

    private static void heapify(int[] arr, int i, int j) {
        int val = arr[i];
        for (int k = 2 * i + 1; k < j; k = 2 * i + 1) {
            if (k + 1 < j && arr[k + 1] > arr[k]) ++k;
            if (arr[k] <= val) break;
            arr[i] = arr[k];
            i = k;
        }
        arr[i] = val;
    }

    /**
     * 计数排序
     *
     * @param arr 排序数组
     */
    static void countSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt(), min = IntStream.of(arr).min().getAsInt();
        int diff = max - min + 1;
        int[] hash = new int[diff];
        for (int a : arr) {
            hash[a - min]++;
        }
        int j = 0;
        for (int i = 0; i < diff; ++i) {
            while (hash[i]-- > 0) {
                arr[j++] = i + min;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = IntStream.of(new int[15]).map(item -> new Random().nextInt(100)).toArray();
        System.out.println(Arrays.toString(arr));
//        bubbleSort(arr);
//        selectSort(arr);
//        insertSort(arr);
//        shellSort(arr);
//        arr = mergeSort(arr);
//        quickSort(arr);
//        heapSort(arr);
//        countSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
